package shortest;

import java.util.Scanner;

public class Dijkstra {

    public static int start = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("输入点和边的数目:");
        int V = sc.nextInt();//总共有多少个点
        int E = sc.nextInt();//总共有多少个边

        int[][] G = new int[V][V];//用来存放图的信息
        int[] d = new int[V];//用来存放从起点到每个点的最短路径长度
        int[] pre = new int[V];//用来存放每个点在其最短路径上的前一个结点
        boolean[] used = new boolean[V];

        System.out.println("依次输入每条边的起点、终点和权值:(点的编号从0开始)");
        for(int i=0; i<E; i++){
            G[sc.nextInt()][sc.nextInt()] = sc.nextInt();
        }

        for(int i=0; i<V; i++){//初始化d
            pre[i] = start;
            if(i==start){
                d[i] = 0;
                continue;
            }
            if(G[start][i]==0)
                d[i] = Integer.MAX_VALUE/E;
            else{
                d[i] = G[start][i];
            }
        }

        int cur = 0;
        used[start] = true;

        while(cur<V){
            int minDis = Integer.MAX_VALUE/E;
            int minIndex = 0;
            for(int i=0; i<V; i++){//每次取d[i]最小的那个点
                if(!used[i] && d[i]<minDis){
                    minDis = d[i];
                    minIndex = i;
                }
            }
            used[minIndex] = true;
            for(int i=0; i<V; i++){
                if(G[minIndex][i]>0 && d[i]>d[minIndex]+G[minIndex][i]){
                    d[i] = d[minIndex]+G[minIndex][i];
                    pre[i] = minIndex;
                }
            }
            cur++;
        }
        for(int i=0; i<V; i++){
            System.out.println("起点"+start+"到点"+i+"的最短路径长度为:"+d[i]);
            System.out.println("最短路径为:");
            int curv = i;
            System.out.print(i+"<-");
            while(true){
                curv = pre[curv];
                if(curv == start)
                    break;
                System.out.print(curv+"<-");
            }
            System.out.println(start);
        }
        sc.close();
    }
}